package _17_剑指Offer;

import java.util.Arrays;

public class _33_剑指Offer二叉搜索树的后序遍历序列 {


    public boolean verifyPostorder(int[] postorder) {
        int n = postorder.length;
        // 找寻左右节点
        int rightIndex = -1;
        int leftIndex = -1;
        for (int i = n - 2; i >= 0; i--) {
            if (leftIndex == -1 && postorder[i] > postorder[n - 1]) {
                rightIndex = i;
            } else if (postorder[i] < postorder[n - 1]) {
                leftIndex = i;
            } else {
                return false;
            }
        }
        // 验证左右子树
        return (rightIndex == - 1 || verifyPostorder(Arrays.copyOfRange(postorder, rightIndex, n - 1)))
                && (leftIndex == -1 || verifyPostorder(Arrays.copyOfRange(postorder, leftIndex, rightIndex == -1? n - 1: rightIndex)));
    }

}
